/*
Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
 */
package com.yuan.algorithms.practice201511;

import java.util.Scanner;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年11月14日 下午12:53:51
 * <br>说明:
 */
public class 最短路 {

	static int MAX = 103;
	static int MAX_VALUE = 1000000;
	static int[][] arc = new int[MAX][MAX];//存储地图
	static int[] way = new int[MAX];//记录路径的长度
	static boolean[] mark = new boolean[MAX];//标记两个街道之间是否已经走过
	
	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		while(in.hasNext()) {
			int n = in.nextInt();
			int m = in.nextInt();
			if (n==0 && m==0) {
				break;
			}
			initialise(n);//初始化数据
			for (int i = 0; i < m; i++) {
				int a = in.nextInt() - 1;
				int b = in.nextInt() - 1;
				int c = in.nextInt();
				if (arc[a][b] > c) {//取两个地点距离的最小值
					arc[a][b] = arc[b][a] = c;//存储街道数据
				}
			}
			int sum = dijkstra(0, n);
			System.out.println(sum);
		}
	}
	private static int dijkstra(int start, int end) {
		for (int i = 0; i < end; i++) {
			way[i] = arc[start][i];//初始化起点到各个街道的距离
		}
		way[start] = 0;//起点到起点的距离为0
		for (int i = 0; i < end - 1; i++) {
			int min = MAX_VALUE;//存储最短距离
			int index = -1;//存储最短距离的下标（街道编号）
			for (int j = 0; j < end; j++) {
				//寻找未到达的距离最短的街道
				if (!mark[j] && way[j] < min) {
					min = way[j];
					index = j;
				}
			}
			mark[index] = true;//标记街道以访问
			for (int j = 0; j < end; j++) {
				//如果搜索到的街道加上走到当前位置的距离优于记录的起点到达当前路径的距离，则更新起点到当前路径的距离
				if (!mark[j] && min+arc[index][j] < way[j]) {
					way[j] = min + arc[index][j];
				}
			}
		}
		return way[end - 1];
	}
	
	private static void initialise(int a) {
		for (int i = 0; i < a; i++) {
			mark[i] = false;
			for (int j = 0; j < a; j++) {
				arc[i][j] = MAX_VALUE;
			}
		}
	}

}
